//
//  main.swift
//  SwiftPro
//
//  Created by chenyh on 2021/3/17.
//

import Foundation

/**
 希尔排序算法在排序过程中会借助一个序列 gap1, gap2, gap3,..., gapt，该序列被称为增 量序列，希尔排序主要通过比较相距 gapk 间隔的元素值的大小来进行排序，每趟排序比较 所使用的间隔距离随着排序的进行而减少，直到只比较相邻元素为止，因此又被叫做“缩 减增量序列”。如果一个数据集中，所有相距 gapk 的元素都被排序，则该数据集是 gapk 排序的。希尔排序具有一个很重要的性质，即一个 gapk 排序的数据集在进行希尔排序的过 程中，会一直保持它的 gapk 排序性。这是希尔算法得以运行的理论基础。
 希尔排序的主要思想是:确定一个元素间隔数 gap，将参加排序的元素从第一个元素
 开始按照这个间隔依次分成多个子序列，分别将所有位置相隔 gap 的元素看成一个子序列。
 
 在这里我们将原数据集划分成 3 个子序列，对于每个子序列本身我们采用其他的排序 算法(如冒泡排序、插入排序等，我们采用冒泡排序)。然后缩小 gap 的值，重新按新的 gap 划分数组，再分别对每个子序列排序，直到 gap 递减为 1。gap 值越大，比较的间距跨 度就越大，当 gap 减少到 1 时，数据就基本有序了。
 增量序列的选择对排序算法的整体性能有很大的影响。目前较为流行的增量序列选择 方法是采用 shell 方法:gapt = n/2 和 gapk = gapk-1/2。下面我们就采用这种增量序列的选取 方法，对数组{3,7,5,1,12,10，8,9}进行希尔排序，如图 5-13 所示。
 
下面的代码中，排序增量 gap 大于 1 时，程序循环执行希尔排序，且每趟排序增量 gap 就会减半。我们选择冒泡排序算法作为每个子序列的自排序算法。
 希尔排序的运行时间是一系列间隔数 gapi 的函数，而且如何选择增量才能产生最好的 排序效果，学术界还没有定论，所以要精确分析希尔排序的时间复杂度是比较困难的。在 某些特定情况下，我们可以估计它的时间复杂度。本文采用 shell 增量获取法，即每次 gap 减半。排序一个具有 n 个元素的数组，gapt = n/2 且 gapk = gapk+1/2，经过 log2n 趟排序以后 就有 gap1=1，因此希尔排序的排序总趟数是 log2n。所以程序中最外层的 while 循环具有 log2n 数量级，内层的循环次数根据子序列所采用的排序算法不同有差距。总的来说，一般认为 希尔排序的时间复杂度在 O(nlog2n)与 O(n2)之间。从上面的代码我们也可以看出，希尔排 序是一种不稳定的排序算法。
 */
func shellsort(data: [Int],n: Int) {
    var data = data;
    var j=0,flag=0,counter = 1,gap=n;
    while gap > 1 {
        gap = gap/2; //采用 shell 增量取法，每次增量减半
        while counter < n && flag == 1 {
            flag = 0;
            for i in 0...n-gap-counter {
                j = i+gap;
                if data[i] > data[j] {
                    (data[i],data[j]) = (data[j],data[i])
                    flag = 1;
                }
            }
        }
    }
}
func main() {
    
}

